package algocasts;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个非空的整数数组，这个数字中有一个整数只出现了一次，其他的整数都出现了多次，找出这个只出现一次的整数。
 */
public class P6_SingleNumber {
    // Time: O(n) Space: O(n)
    public int singleNumber_Set(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int sum = 0, uniqueSum = 0;
        // 计算 去重之后数组的和 以及 原来数组的和
        for (int num : nums) {
            if (!set.contains(num)) {
                uniqueSum += num;
                set.add(num);
            }
            sum += num;
        }
        // 2*去重数组的和 - 原来数组的和 = 出现一次的数
        return 2 * uniqueSum - sum;
    }

    // Time: O(n) Space: O(1)  异或运算
    public int singleNumber_Xor(int[] nums) {
        // 相同的数异或之后为0，整个数组的数进行异或操作，最后得到的就是只出现一次的数
        int result = 0;
        for (int num : nums) result ^= num;
        return result;
    }


    public static void main(String[] args) {
        P6_SingleNumber solution = new P6_SingleNumber();
        int[] nums = {1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 8, 7, 7, 6, 6};
        System.out.println(solution.singleNumber_Set(nums));
        System.out.println(solution.singleNumber_Xor(nums));
    }
}
